package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         265,
		Discription: "k种颜色的粉刷房子",
		Level:       3,
		Labels: map[string]int{
			"动态规划":  1,
			"有限状态机": 1,
			"空间复用": 1,
		},
	})
}

func MinCostII(costs [][]int) int {
	n := len(costs)
	k := len(costs[0])
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, k)
	}

	var minCostColor, secMinCostColor int
	if costs[0][0] <= costs[0][1] {
		minCostColor = 0
		secMinCostColor = 1
	} else {
		minCostColor = 1
		secMinCostColor = 0
	}
	for j := 0; j < k; j++ {
		dp[0][j] = costs[0][j]
		if j > 1 {
			if dp[0][j] < dp[0][minCostColor] {
				secMinCostColor = minCostColor
				minCostColor = j
			} else if dp[0][j] < dp[0][secMinCostColor] {
				secMinCostColor = j
			}
		}
	}

	for i := 1; i < n; i++ {
		//维护当前的最小和次小值，结束遍历覆盖minCostColor，secMinCostColor
		var curMin, curSecMin int

		for j := 0; j < k; j++ {
			//还可以复用空间
			if j != minCostColor {
				dp[i][j] = dp[i-1][minCostColor] + costs[i][j]
			} else {
				dp[i][j] = dp[i-1][secMinCostColor] + costs[i][j]
			}

			if j == 1 {
				if dp[i][0] <= dp[i][1] {
					curMin = 0
					curSecMin = 1
				} else {
					curMin = 1
					curSecMin = 0
				}
			} else if j > 1 {
				if dp[i][j] < dp[i][curMin] {
					curSecMin = curMin
					curMin = j
				} else if dp[i][j] < dp[i][curSecMin] {
					curSecMin = j
				}
			}
		}

		minCostColor = curMin
		secMinCostColor = curSecMin
	}

	return dp[n-1][minCostColor]
}